#include "LinkList.h"
#include <stddef.h>

/******************************************************************************
 *函数名称：  ListManageInit
 *输入参数：  listManage,链表管理器地址
 *输出参数：  无
 *返回值  ：  无
 *功能描述：  初始化链表管理器，此管理器一定是用户声明的变量
 ******************************************************************************/
void ListManageInit (LIST_MANAGE *listManage)
{
	listManage->head = NULL;
	listManage->tail = NULL;
	listManage->count = 0;
}

/******************************************************************************
 *函数名称：  ListLength
 *输入参数：  listManage,链表管理器地址
 *输出参数：  无
 *返回值  ：  链表数据个数
 *功能描述：  获取链表数据的个数
 ******************************************************************************/
uint32_t ListLength (const LIST_MANAGE *listManage)
{
	return (listManage->count);
}

/******************************************************************************
 *函数名称：  ListPeekHead
 *输入参数：  listManage,链表管理器地址
 *输出参数：  readNode,获取的节点地址
 *返回值  ：  获取成败信息
 *功能描述：  获取首节点地址
 ******************************************************************************/
LIST_RETURN ListPeekHead(const LIST_MANAGE *listManage, LIST_NODE **readNode)
{
	*readNode = listManage->head;
	return L_OK;
}

void *vListPeekHead(const LIST_MANAGE *listManage)
{
	LIST_NODE *ret = NULL;
	ListPeekHead(listManage, &ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListPeekTail
 *输入参数：  listManage,链表管理器地址
 *输出参数：  readNode,获取的节点地址
 *返回值  ：  获取成败信息
 *功能描述：  获取尾节点地址
 ******************************************************************************/
LIST_RETURN ListPeekTail(const LIST_MANAGE *listManage, LIST_NODE **readNode)
{
	*readNode = listManage->tail;
	return L_OK;
}

void * vListPeekTail(const LIST_MANAGE *listManage)
{
	LIST_NODE *ret = NULL;
	ListPeekTail(listManage, &ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListPeekNext
 *输入参数：  listNode,已知节点
 *输出参数：  readNode,获取的节点地址
 *返回值  ：  获取成败信息
 *功能描述：  获取已知节点的下一个节点
 ******************************************************************************/
LIST_RETURN ListPeekNext(const LIST_NODE *listNode, LIST_NODE **readNode)
{
	*readNode = listNode->next;
	return L_OK;
}

void * vListPeekNext(const LIST_NODE *listNode)
{	
	return listNode->next;
}

/******************************************************************************
 *函数名称：  ListPeekPrev
 *输入参数：  listNode,已知节点
 *输出参数：  readNode,获取的节点地址
 *返回值  ：  获取成败信息
 *功能描述：  获取已知节点的上一个节点
 ******************************************************************************/
LIST_RETURN ListPeekPrev(const LIST_NODE *listNode, LIST_NODE **readNode)
{
	*readNode = listNode->prev;
	return L_OK;
}
void *vListPeekPrev(const LIST_NODE *listNode)
{
	return listNode->prev;
}

/******************************************************************************
 *函数名称：  ListPeekIndex
 *输入参数：  listManage,链表管理器
 *			  index,索引，如果是负数，则表示从后向前搜索
 *输出参数：  readNode,获取的节点地址
 *返回值  ：  获取成败信息
 *功能描述：  根据索引获取节点
 ******************************************************************************/
LIST_RETURN ListPeekIndex(const LIST_MANAGE *listManage, int32_t index, LIST_NODE **readNodes)
{
	long i = 0;
	LIST_NODE *pln = NULL;
	
	*readNodes =  NULL;
	ListPeekHead(listManage, &pln);
	//如果链表为空，则退出 
	if(pln == NULL) {		
		return L_EMPTY;
	}
	//如果索引大于链表总长度，则退出 
	if(index >=  listManage->count) {		//正数大于链表长度 
		return L_OUTINDEX;
	} else if(index < -(listManage->count)) {	//负数小于链表长度的相反数 
		return L_OUTINDEX;
	}
	
	if(index >= 0 ) {
		ListPeekHead(listManage, &pln);			//正数从前到后搜索 
		for(i = 0; i < index; i++) {
			ListPeekNext(pln, &pln);
		}
	} else {
		ListPeekTail(listManage, &pln);			//负数从后到前搜索 
		for(i = -1; i > index; i--) {
			ListPeekPrev(pln, &pln);
		}
	}
	
	*readNodes = pln;
	
	return L_OK;
}
void * vListPeekIndex(const LIST_MANAGE *listManage, int32_t index)
{
	LIST_NODE *ret = NULL;
	ListPeekIndex(listManage, index,&ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListPeekItem
 *输入参数：  listManage,链表管理器
 *			  listNode,已知节点
 *输出参数：  index,索引的地址
 *返回值  ：  获取成败信息
 *功能描述：  根据节点获取索引
 ******************************************************************************/
LIST_RETURN ListPeekItem(const LIST_MANAGE *listManage, const LIST_NODE *listNode,  int32_t *index)
{
	*index = -1;
	int32_t i = 0;
	LIST_NODE *pln;
	//从头到尾遍历节点
	for (ListPeekHead(listManage, &pln); pln != NULL; ListPeekNext(pln, &pln)) {  		
		if(pln == listNode) {
			*index = i;
			break;	
		}
		i++;
	}
	
	if(*index != -1) {
		return L_OK;
	} else {
		return L_NOTHAVE;
	}		
}

int32_t vListPeekItem(const LIST_MANAGE *listManage, const LIST_NODE *listNode)
{
	int32_t i = -1;
	ListPeekItem(listManage, listNode, &i);
	
	return i;
}

/******************************************************************************
 *函数名称：  ListPutHead
 *输入参数：  listManage,链表管理器
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入到链表首位置
 ******************************************************************************/
LIST_RETURN ListPutHead(LIST_MANAGE *listManage, LIST_NODE *lnew)
{
	int32_t index;
	//如果新节点已经存在，则不做任何动作 ,返回重复信息
	if(ListPeekItem(listManage, lnew, &index) == L_OK) 
		return L_REPEAT;
	
	lnew->prev = NULL;
	lnew->next = listManage->head;	
		
	if (listManage->head == NULL) {	
		//如果原来就是空链表，则新节点既是头节点，也是尾节点
		listManage->tail = lnew;
	}
	else {
		//原来的头节点的前节点改为新节点
		listManage->head->prev = lnew;
	}
	//更新链表管理器头节点
	listManage->head = lnew;
	//数据量增加
	listManage->count++;
	
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListPutTail
 *输入参数：  listManage,链表管理器
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入到链表尾位置
 ******************************************************************************/
LIST_RETURN ListPutTail(LIST_MANAGE *listManage, LIST_NODE *lnew)
{
	int32_t index;
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew, &index) == L_OK) 
		return L_REPEAT;
	
	lnew->prev = listManage->tail;		//新节点上一个元素指向原链表尾指针 
	lnew->next = NULL;
	
	if (listManage->tail == NULL) {    		//如果头指针为空，表明原链表无数据，
		listManage->head = lnew;			//新节点成为链表的头 
	}
	else {
		listManage->tail->next = lnew;		//否则，就把原链表的尾元素的下一个链接到新节点上 
	}
	
	listManage->tail = lnew;				//之后把链表管理器的尾指针指向新元素 
	listManage->count++; 
	
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListInsertBeforItem
 *输入参数：  listManage,链表管理器
 *			  listNode,已知节点
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入已知节点的前边
 ******************************************************************************/
LIST_RETURN ListInsertBeforItem(LIST_MANAGE *listManage, LIST_NODE *listNode, LIST_NODE *lnew)
{
	int32_t index;
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew, &index) == L_OK) 
		return L_REPEAT;
	
	//如果已知节点不在链表里，退出 
	if(ListPeekItem(listManage, listNode, &index) != L_OK) 
		return L_NOTHAVE;
	
	//更新新节点的前后节点信息
	lnew->next = listNode;
	lnew->prev = listNode->prev;
	
	if (listNode->prev == NULL) {
		//如果已知节点没有前节点，
		//则表示已知节点为原来的首节点
		//此时把首节点更新成输入的新节点
		listManage->head = lnew;
	}
	else {
		//把已知节点的前节点的后节点改为输入的新节点，完成更新
		listNode->prev->next = lnew;
	}
	
	//更新已知节点的前节点为输入的新节点
	listNode->prev = lnew;
	listManage->count++; 
	
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListInsertAfterItem
 *输入参数：  listManage,链表管理器
 *			  listNode,已知节点
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入已知节点的后边
 ******************************************************************************/
LIST_RETURN ListInsertAfterItem(LIST_MANAGE *listManage, LIST_NODE *listNode, LIST_NODE *lnew)
{
	int32_t index;
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew, &index) == L_OK) 
		return L_REPEAT;
	
	//如果已知节点不在链表里，退出 
	if(ListPeekItem(listManage, listNode, &index) != L_OK) 
		return L_NOTHAVE;
	
	lnew->next = listNode->next;
	lnew->prev = listNode;
	
	if (listNode->next == NULL) {    
		listManage->tail = lnew;
	}
	else {
		listNode->next->prev = lnew;
	}
	
	listNode->next = lnew;
	listManage->count++; 
	
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListInsertBeforIndex
 *输入参数：  listManage,链表管理器
 *			  index,指定索引，可以是负数
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入指定索引的前边
 ******************************************************************************/
LIST_RETURN ListInsertBeforIndex(LIST_MANAGE *listManage, int32_t index, LIST_NODE *lnew)
{
	int32_t i;
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew, &i) == L_OK) 
		return L_REPEAT;
	
	LIST_NODE *listNode = NULL;
	ListPeekIndex(listManage, index, &listNode);
	
	if(listNode == NULL) {
		return L_OUTINDEX;
	} else {
		ListInsertBeforItem(listManage, listNode, lnew);
		return L_OK;
	}
}

/******************************************************************************
 *函数名称：  ListInsertAfterIndex
 *输入参数：  listManage,链表管理器
 *			  index,指定索引，可以是负数
 *			  lnew,新节点
 *输出参数：  无
 *返回值  ：  获取成败信息
 *功能描述：  新节点插入指定索引的后边
 ******************************************************************************/
LIST_RETURN ListInsertAfterIndex(LIST_MANAGE *listManage, int32_t index, LIST_NODE *lnew)
{
	int32_t i;
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew, &i) == L_OK) 
		return L_REPEAT;
	
	LIST_NODE *listNode = NULL;
	ListPeekIndex(listManage, index, &listNode);
	
	if(listNode == NULL) {
		return L_OUTINDEX;
	} else {
		ListInsertAfterItem(listManage, listNode, lnew);
		return L_OK;
	}
}

/******************************************************************************
 *函数名称：  ListPopHead
 *输入参数：  listManage,链表管理器
 *输出参数：  out, 要删除的节点，若为NULL表示删除失败
 *返回值  ：  成败信息
 *功能描述：  删除首节点
 ******************************************************************************/
LIST_RETURN ListPopHead(LIST_MANAGE *listManage, LIST_NODE **out)
{
	LIST_NODE *listNode = NULL;
	
	//获取原链表首节点
	listNode = listManage->head;
	
	if (listNode != NULL) {
		//更新链表管理器的首节点为原来的第二个节点
		listManage->head = listNode->next;
		
		if (listNode->next == NULL) {
			//如果原来首节点的第二个节点为空
			//则表示原来只有一个节点；
			//此时节点为空，更新尾节点也为空
			listManage->tail = NULL;
		}
		else {
			//更新原来链表中第二个节点的前指针为空
			listNode->next->prev = NULL;
		}
	} else {
		//如果原链表首节点为空，则直接退出
		return L_EMPTY;
	}
	
	listManage->count--; 
	*out = listNode;	
	
	return L_OK;
}

void *vListPopHead(LIST_MANAGE *listManage)
{
	LIST_NODE *ret; 
	ListPopHead(listManage, &ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListPopEnd
 *输入参数：  listManage,链表管理器
 *输出参数：  out, 要删除的节点，若为NULL表示删除失败
 *返回值  ：  成败信息
 *功能描述：  删除尾节点
 ******************************************************************************/
LIST_RETURN ListPopEnd(LIST_MANAGE *listManage, LIST_NODE **out)
{
	LIST_NODE *listNode;
	
	listNode = listManage->tail;
	
	if (listNode != NULL) {
		listManage->tail = listNode->prev;
		
		if (listNode->prev == NULL) {
			listManage->head = NULL;
		}
		else {
			listNode->prev->next = NULL;
		}
	} else {
		return L_EMPTY;
	}
	
	listManage->count--; 
	*out = listNode;
	
	return L_OK;
}

void *vListPopEnd(LIST_MANAGE *listManage)
{
	LIST_NODE *ret; 
	ListPopEnd(listManage, &ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListPopItem
 *输入参数：  listManage,链表管理器
 *			  listNode,要删除的节点
 *输出参数：  无
 *返回值  ：  成败信息
 *功能描述：  删除指定节点
 ******************************************************************************/
LIST_RETURN ListPopItem(LIST_MANAGE *listManage, LIST_NODE *listNode)
{
	int32_t i;
	if(ListPeekItem(listManage, listNode, &i) != L_OK) 
		return L_NOTHAVE;
	
	if (listNode->next == NULL) {
		listManage->tail = listNode->prev;
	} else {
		listNode->next->prev = listNode->prev;
	}
	
	if (listNode->prev == NULL) {
		listManage->head = listNode->next;
	}
	else {
		listNode->prev->next = listNode->next;
	}
	listManage->count--; 
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListPopIndex
 *输入参数：  listManage,链表管理器
 *			  index,要删除的节点索引，可以为负数
 *输出参数：  out, 要删除的节点，若为NULL表示删除失败
 *返回值  ：  成败信息
 *功能描述：  删除指定索引的节点
 ******************************************************************************/
LIST_RETURN ListPopIndex(LIST_MANAGE *listManage, int32_t index, LIST_NODE **out)
{
	LIST_NODE *listNode = NULL;
	ListPeekIndex(listManage, index, &listNode); 
	
	*out = listNode;
	
	if(listNode == NULL) {
		return L_OUTINDEX;
	} else {
		return ListPopItem(listManage, listNode);
	}	
}

void *vListPopIndex(LIST_MANAGE *listManage, int32_t index)
{
	LIST_NODE *ret; 
	ListPopIndex(listManage, index, &ret);
	
	return ret;
}

/******************************************************************************
 *函数名称：  ListSwitchItems
 *输入参数：  listManage,链表管理器
 *			  node1、node2,要交换的两个节点
 *输出参数：  无
 *返回值  ：  成败信息
 *功能描述：  交换两个指定的节点
 ******************************************************************************/
LIST_RETURN ListSwitchItems(LIST_MANAGE *listManage, LIST_NODE *node1, LIST_NODE *node2)
{
	//用于保存其中一个节点的信息，用于交换 
	//注意是数据不是指针，否则就是野指针
	LIST_NODE lspnode;				
	int32_t i;
	
	//两个节点如果有一个不在原链表中，就退出
	if(ListPeekItem(listManage, node1, &i) != L_OK) 
		return L_NOTHAVE;
	if(ListPeekItem(listManage, node2, &i) != L_OK) 
		return L_NOTHAVE;
	
	//如果两个节点相邻
	if(node1->next == node2){
		//node1的前节点的后指针指向node2
		//node2的后节点的前指针指向node1
		if(node1->prev != NULL)
			node1->prev->next = node2;
		if(node2->next != NULL)	
			node2->next->prev = node1;
		//交换node1、node2的前后指针
		node1->next = node2->next;		
		node2->next = node1;
		node2->prev = node1->prev; 
		node1->prev = node2;
	} else if(node2->next == node1){
		//如果node2在node1前边，
		//则递归调用本函数
		//更换参数顺序
		//执行完直接退出
		return ListSwitchItems(listManage, node2, node1);		
	} else {
		//如果两个节点不相邻
		
		//先交换两个节点相邻的四个节点的值 
		if(node1->prev != NULL)
			node1->prev->next = node2;
		if(node1->next != NULL)	
			node1->next->prev = node2;
		if(node2->prev != NULL)
			node2->prev->next = node1;
		if(node2->next != NULL)	
			node2->next->prev = node1;
		
		//再交换两个节点的数据	
		lspnode.next = node1->next;
		lspnode.prev = node1->prev;
		node1->next = node2->next;
		node1->prev = node2->prev;
		node2->next = lspnode.next;
		node2->prev = lspnode.prev;
	}   
	
	//判断交换后两个节点是否是链表的收尾节点
	//如果是，则更新链表管理器
	if(node1->next == NULL) {
		listManage->tail = node1;
	} else if(node2->next == NULL) {
		listManage->tail = node2;
	}
	
	if(node1->prev == NULL) {
		listManage->head = node1;
	} else if(node2->prev == NULL) {
		listManage->head = node2;
	}
	
	return L_OK;
}

/******************************************************************************
 *函数名称：  ListSwitchIndex
 *输入参数：  listManage,链表管理器
 *			  index1、index1,要交换的两个节点的索引
 *输出参数：  无
 *返回值  ：  成败信息
 *功能描述：  交换两个指定索引的节点
 ******************************************************************************/
LIST_RETURN ListSwitchIndex(LIST_MANAGE *listManage, int32_t index1,int32_t index2)
{
	LIST_NODE *node1 = NULL;	
	LIST_NODE *node2 = NULL;
	
	if(ListPeekIndex(listManage, index1, &node1) != L_OK)
		return L_OUTINDEX;	
	if(ListPeekIndex(listManage, index2, &node2) != L_OK)
		return L_OUTINDEX;
	
	return ListSwitchItems(listManage, node1, node2);
}

/******************************************************************************
 *函数名称：  ListSort
 *输入参数：  listManage,链表管理器
 *			  s2b,从小到大排列，TRUE为从小到大，FALSE为从大到小 
 *			  fun_compare,用户编写的比较策略回调函数
 *输出参数：  无
 *返回值  ：  成败信息
 *功能描述：  链表排序
 ******************************************************************************/
LIST_RETURN ListSort(LIST_MANAGE *listManage, bool s2b, FUN_COMPARE fun_compare)
{
	LIST_NODE *pNode = NULL;		//前节点	
	LIST_NODE *tNode = NULL;		//后节点
	LIST_NODE *mNode = NULL;		//暂存节点
	int comp;						//回调函数的判断结果
	
	//获取收尾节点
	ListPeekHead(listManage, &pNode); 		
	ListPeekNext(pNode, &tNode);	
	
	//判断链表是否为空
	if((pNode == NULL) || (tNode == NULL))
		return L_EMPTY;
	
	//使用选择排序方法进行排序 
	//算法原理参考视频1:31位置  https://b23.tv/bYDnA2N
	while(tNode != NULL) {
		while(tNode != NULL) {
			//通过回调函数获取排序依据的结果
			comp = fun_compare(pNode, tNode) ;
			
			//根据参数确定排序顺序（从大到小还是从小到大）
			if(!s2b)  
				comp = -comp;
			
			if(comp > 0) {
				//链表位置交换 
				ListSwitchItems(listManage, pNode, tNode);
				
				//经过上边的代码，pNode和tNode的前后指针都做了修改
				//但是循环的时候还需要按照以前的位置继续迭代
				//所以这里又把指针变量交换回来（链表顺序没有变）
				//判断节点的交换 
				mNode = pNode;
				pNode = tNode;
				tNode = mNode;
			}
			//获取下一个后节点
			ListPeekNext(tNode, &tNode);
		}
		//获取下一个前节点
		ListPeekNext(pNode, &pNode);
		//把前节点的后指针赋给后节点
		ListPeekNext(pNode, &tNode);			
	} 
	return L_OK;
}

